package com.li.sort.arithmetic;

import java.util.Arrays;
import java.util.Random;

public class CountSort {
	public static final int SIZE = 100;
	public static void main(String[] args) {
		int[] array = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			array[i] = random.nextInt(100);
		}

		//System.out.println(Arrays.toString(array));
		long time1= System.currentTimeMillis();
		countSort(array);
		System.out.println(Arrays.toString(array));
		System.out.println(System.currentTimeMillis()-time1);
	}

	/**
	 * n-1趟排序就ok
	 * @param array
	 */
	public static void countSort(int[] array){
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		for(int i=0;i<array.length;i++){
			max = Math.max(max, array[i]);
			min = Math.min(min, array[i]);
		}

		int[] help = new int[max+1-min];
		for(int i=0;i<array.length;i++){
			int maxPos = array[i]-min;
			help[maxPos]++;
		}
		int index = 0;
		for(int i=0;i<help.length;i++){
			while(help[i]-->0){
				array[index++] = i+min;
			}
		}
	}

	public static void swap(int[] array,int i,int j){
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}
